import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Leetcode {
}

//leetcode:139:单词拆分
class Solution1 {
    public boolean wordBreak(String s, List<String> wordDict) {
        //优化：将字典中的值放入set中，方便进行快速查找
        Set<String> set = new HashSet<>(wordDict);
        int n = s.length();
        //创建一个dp表表示以i位置为结尾的字符串是否可以被字典中的元素拼接
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        s = " "+ s;

        for(int i = 1; i <= n; i++){
            for(int j = i; j >= 1; j--){
                //判断j位置前的字符串是否可以是拼接成的，同时判断j到i位置的字符串是否再字典中
                if(dp[j-1] && set.contains(s.substring(j,i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

//leetcode:467:环绕字符串中唯一的子字符串
class Solution2 {
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();

        //创建一个dp表：以i位置为结尾所有子字符串有多少个在base中出现
        int[] dp = new int[n];
        //如果为单个字符那么必定为1
        for(int i = 0; i < n; i++) dp[i] = 1;

        for(int i = 1; i < n; i++){
            //如果字符是连续的并且'a'的前面是'z'
            if(ch[i-1] + 1 == ch[i] || ch[i] == 'a' && ch[i-1] == 'z'){
                //那么i位置为结尾的所有子字符串的个数就为这个位置的值加上前面的所有子字符串的个数
                dp[i] += dp[i-1];
            }
        }

        //由于重复的子字符串不做计算，所以我们要进行去重
        int[] hash = new int[26];
        for(int i = 0; i < n; i++){
            //如果以某个相同位置为结尾，dp值更大的会包含小的所有子字符串
            hash[ch[i] - 'a'] = Math.max(hash[ch[i] - 'a'] , dp[i]);
        }

        //计算所有以某个字符为结尾的所有子字符串个数
        int ret = 0;
        for(int x : hash){
            ret += x;
        }
        return ret;
    }
}